package com.example.demo;

import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.Stack;

public class AllDemo {

    /**
     * 两个list 取交集 并集
     */

    /**
     * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
     *
     * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
     *
     * 注意：给定 n 是一个正整数。
     *
     * 示例 1：
     *
     * 输入：2
     * 输出：2
     * 解释： 有两种方法可以爬到楼顶。
     *
     * 1. 1 阶 + 1 阶
     * 2. 2 阶
     * 示例 2：
     *
     * 输入：3
     * 输出：3
     * 解释： 有三种方法可以爬到楼顶。
     *
     * 1. 1 阶 + 1 阶 + 1 阶
     * 2. 1 阶 + 2 阶
     * 3. 2 阶 + 1 阶
     */

    public static int loop(int n){
        if(n<=0){
            return 0;
        }
        int[] results = new int[n+1];
        results[1] = 1;
        results[2] = 2;
        results[3] = 3;
        for(int i=4;i<=n;i++){
            results[i] = results[i-1]+results[i-2];
        }

        return results[n];
    }

    @Test
    public void test(){
        int loop = loop(-1);
        System.out.println(loop);
    }




    /**
     * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
     *
     * 示例:
     *
     * 输入: [-2,1,-3,4,-1,2,1,-5,4],
     * 输出: 6
     * 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
     */
    public static int returnLarge1(int nums[]){
        int fast = 1;
        int slow = 0;
        for(int i=0;i<nums.length-1;i++){
            int temp = 0;
            for(int j = slow;j<= fast;j++){
                temp = temp+nums[j];
            }
            if(temp>=nums[fast]){
                fast++;
            }else {
                slow++;
                fast++;
            }
        }
        int result = 0;
        for(int i=slow;i<=fast;i++){
            result = result + nums[i];
        }
        return result;
    }
    public static int returnLarge(int nums[]){
        if(nums==null || nums.length==0){
            return 0;
        }
        int results[] = new int[nums.length];

        //k个元素最大
        int result = 0;
        results[0] = nums[0];
        for(int i=1;i<nums.length;i++){
            results[i] = Math.max(results[i - 1], 0) + nums[i];
            //results[i] = Math.max(Math.max(nums[i],results[i-1]),nums[i]);
            result = results[i]>result?results[i]:result;
        }

        return result;
    }

    @Test
    public void testreturnLarge(){
        int nums [] = {-2,1,-3,4,-1,2,1,-5,4};
        System.out.println(returnLarge1(nums));
    }


    /**
     * 给定一个无序的整数数组，找到其中最长上升子序列的长度。
     *
     * 示例:
     *
     * 输入: [10,9,2,5,3,7,101,18]
     * 输出: 4
     * 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
     */
    @Test
    public void testlargeSort(){
        int nums[] = {10,9,2,5,3,7,101,18};
        int i = lengthOfLIS(nums);
        System.out.println(i);
    }

    // 有贪心选择的意思
    public static int lengthOfLIS(int[] nums) {
        int len = nums.length;
        // 先考虑极端输入
        if (len <= 1) {
            return len;
        }
        // tail 数组的定义：长度为 i+1 的上升子序列的末尾最小是几
        int[] tail = new int[len];
        // 遍历一遍整个数组，使用二分查找算法
        tail[0] = nums[0];
        int res = 0;
        for (int i = 1; i < len; i++) {
            // 比 tail 数组实际有效的末尾的那个元素还大
            if (nums[i] > tail[res]) {
                // 直接添加在那个元素的后面
                tail[++res] = nums[i];
            } else {
                // 二分查找到第 1 个比 nums[i] 还大的元素，更新到那个位置
                int l = 0;
                int r = res;
                while (l < r) {
                    int mid = l + (r - l) / 2;
                    // 有就啥都不做了
                    if (tail[mid] == nums[i]) {
                        l = mid;
                        break;
                    } else if (tail[mid] >= nums[i]) {
                        r = mid;
                    } else {
                        l = mid + 1;
                    }
                }
                tail[l] = nums[i];
            }
           printArray(nums[i], tail);
        }
        return ++res;
    }


    // 调试方法，以观察是否运行正确
    private static void printArray(int num, int[] tail) {
        System.out.print("当前数字：" + num);
        System.out.print("\t当前 tail 数组：");
        int len = tail.length;
        for (int i = 0; i < len; i++) {
            if (tail[i] == 0) {
                break;
            }
            System.out.print(tail[i] + ", ");
        }
        System.out.println();
    }


    public static int largeSort(int nums[]){
        //1. 穷举法
        //2. 假设最长子串为结尾为i，和i-1的关系
        // i if num[i] > nums[i-1]
        //dp[i] = dp[i-1] + if(nums[i]>nums[i-1] return +1) else
        if(nums==null || nums.length == 0){
            return 0;
        }

        int results [] = new int[nums.length];
        Arrays.fill(results,1);
        //results[0] = 1;
        int result = 0 ;
        for(int i=0;i<nums.length;i++){
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    results[i] =Math.max(results[j]+1,results[i]);
                }
            }
            result = results[i]>result?results[i]:result;
        }
        return result;
    }



    /**
     * 二分查找
     */
    @Test
    public void testBinarySearch(){
        int nums[] = {10,9,2,5,3,7,101,18};
        Arrays.sort(nums);
        System.out.println(Arrays.toString(nums));
        int i = binarySearch(nums, 9);
        System.out.println(i);
    }
    public static int binarySearch(int nums[] ,int target){
        if(nums==null || nums.length==0){
            return -1;
        }
        int start = 0;
        int end = nums.length-1;

        while (end>=start){
            int mid = start+((end-start)>>>2);
            if(nums[mid]>target){
                end = mid -1;
            }else if(nums[mid]<target) {
                start = mid+1;
            }else {
                return mid;
            }
        }
        return -1;
    }

    /**
     * 6.2 全排列问题
     * 问题描述：
     *   有1，2，3，4个数，问你有多少种排列方法，并输出排列。
     */
    public static void main(String[] args) {
       int nums[ ]  = {1,2,3};
       allSort(nums,0,2);
    }

    //
    public static void allSort(int nums [],int start,int end){
        if(start == end ){
            for(int temp:nums){
                System.out.print(temp);
            }
            System.out.println();
        }
        //全排列  123
        /**
         *  1 2 3   2 3  3   start end  start+1 end
         *  1 3 2
         *  2 1 3
         *  2 3 1
         *  3 1 2
         *  3 2 1
         */
        for(int i=start;i<=end;i++){
            swap(nums,i,start);
            allSort(nums,start+1,end);
            swap(nums,i,start);
        }

    }

    private static void swap(int [] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    /**
     * 快排 1个的 两个的
     */
    @Test
    public void testquickSort(){
        int nums[] = {1,2,3,4,5,7};
        quickSort(nums);
        for(int i =0;i<nums.length;i++){
            System.out.print(nums[i]+"\t");
        }
    }
    public static void quickSort(int nums[]){
        quickSort(nums,0,nums.length-1);
    }

    //递归的思想 每次方法的执行过程一样，不用过分关心程序执行的每一步
    private static void quickSort(int[] nums, int start, int end) {
        if(start>=end ){
            return;
        }
        //找到中间值 返回中间位置
        int middle = findmiddle(nums,start ,end);
        quickSort(nums,start,middle-1);
        quickSort(nums,middle+1,end);
    }

    private static int findmiddle(int[] nums, int start, int end) {
        //假设标准值为第一个
//        System.out.println("未排序");
//        print(nums);
//        System.out.println();
       int standard =  nums[start];
       //中间值位置
       int result = start;

        //1001	10000	1	2	3	4	5
        // 1001 10000  1 2 3 4 5
        // 1001 10000  1 2 3 4 5
        // 1001 1 2 3 4 5 10000
        //
        // 5 1 2 6 7 -> 1 2 5 6 7
       for(int i=start+1;i<=end;i++){
           if(nums[i]<standard){
               result++;
               swap(nums,i,result);
           }
       }
       swap(nums,result,start);

        System.out.println();
        System.out.println("已排序,result为" + result);
        print(nums);
        System.out.println();
        return result;
    }

    private static int partition(int[] arr, int startIndex,int endIndex) {

        System.out.println("未排序");
        print(arr);
        System.out.println();
        int left = startIndex;
        int right = endIndex;
        int pivot = arr[startIndex];//取第一个元素为基准值
        //1001	10000	1	2	3	4	5
        //1001 5 1 2 3 4 10000
        //-1,-2,200032,1001,10000,1,2,3,4,5,-1,22
        //-1 -
       while(true){
           while(arr[right]>=pivot&&left<right){
               right--;
               if(left == right){
                   break;
               }
           }
           while(arr[left]<=pivot&&left<right){
               left++;
               if(left == right){
                   break;
               }
           }

           swap(arr,left,right);
           if(left == right){
               break;
           }

       }
        swap(arr,right,startIndex);
        //将基准值插入序列

        System.out.println();
        System.out.println("已排序,result为" + right);
        print(arr);
        System.out.println();
        return right;
    }

    /**
     * 冒泡排序
     */
    public static void sort11(int nums[]){
        for(int i=0;i<nums.length-1;i++){
            boolean flag = true;
            for(int j=i+1;j< nums.length;j++){

                if(nums[i]>nums[j]){
                    flag = false;
                    swap(nums,j,i);
                }
            }
            if(flag){
               break;
            }
        }
    }

    @Test
    public void testSelectSort(){
        int nums [] = {1,-1,2,-2,3,4,5};
        selectSort(nums);
        print(nums);

    }
    public static void print(int nums[]){
        for(int i=0;i<nums.length;i++){
            System.out.print(nums[i]+"\t");
        }
    }
    /**
     * 选择排序
     * // 1 -1 2 3 4 5
     * // -1 1 2 3 4 5
     * // 1,-1,2,-2,3,4,5
     * // -1 1 2 -2 3 4 5
     * 找到最大的元素依次放到最前面
     */
    public static void selectSort(int [] arr){
       if(arr==null || arr.length==0){
           return;
       }
       for(int i=0;i<arr.length;i++){
           int min =i;
           for(int j=i+1;j<arr.length;j++){
               if(arr[i]>arr[j]){
                   min = j;
               }

           }
           swap(arr,min,i);
       }

    }
    /**
     *
     */
    @Test
    public void testsortJi(){
        int nums []= {10,2,3,4,5,6,7,11,2232,434345,1123};
        sortJiDouble(nums);
        print(nums);
    }


    /**
     * 奇数放前 偶数放后
     * @param nums
     */
    public static void sortJiDouble(int nums[]){
        if(nums==null || nums.length ==0){

        }
        int left = 0; int right = nums.length-1;
        while(true){
            while(isJI(nums[left]) ){
                if(left<right){
                    left++;
                }else if(left==right){
                    break;
                }
            }

            while(!isJI(nums[right] )){
                if(left<right){
                    right--;
                }else if(left==right){
                    break;
                }
            }
            swap(nums,left,right);
            if(left==right){
                break;
            }

        }
    }
    public static void sortJi(int nums []){

        int temp = nums.length-1;
        // 从前开始找 如何使偶数放最后面 temp 偶数应该放的位置

        for( int i=0;i<nums.length;){
            int num = nums[i];
            if(!isJI(num)){
                swap(nums,i,temp);
                temp--;
            }else {
                i++;
            }
            if(i==temp){
                break;
            }
        }
    }

    private static boolean isJI(int nums){
        boolean result = false;
        if(nums%2!=0){
            result = true;
        }
        return result;
    }

    @Test
    public void testGetIndex(){
        int [] nums={1,2,3,4,5,6,7};
        int index = binarySearch1(nums, 7);
        System.out.println(index);
    }
    /**
     * //二分查找 左边界 有边界
     */
    public static int getIndex(int [] nums,int target){
        if(nums ==null || nums.length==0){
            return -1;
        }
        int start = 0;
        int end = nums.length-1;
        return getIndex(nums,target,start,end);
    }
    public static int getIndex(int [] nums,int target,int start,int end){
        int mid = start+(end-start)/2;
        if(nums[mid] ==target){
            return mid;
        }else if(nums[mid]>target){
            return getIndex(nums,target,mid-1,start);
        }else {
            return getIndex(nums,target,mid+1,end);
        }
    }


    public static int binarySearch1(int [] nums,int target){
        if(nums ==null || nums.length==0){
            return -1;
        }
        int start = 0;
        int end = nums.length-1;

        while(end>=start){
            int mid  = start+(end-start)/2;
            if(nums[mid]==target){
                return mid;
            }else if(nums[mid]>target){
                end = mid-1;
            }else {
                start = mid+1;
            }
        }
        return -1;
    }

    /**
     * 输入: nums = [5,7,7,8,8,10], target = 8
     * 输出: [3,4]
     * 返回起始位置
     *
     * 输入: nums = [5,7,7,8,8,10], target = 6
     * 输出: [-1,-1]
     */
    @Test
    public void testgetIndex1(){
        int nums [] = {5,7,7,8,8,10};
        int[] index1 = getIndex1(nums, 10);
        System.out.println(Arrays.toString(index1));
    }
    public static int[] getIndex1(int nums[],int target){
        int result [] = new int[2];
        result[0] = -1;
        result[1] = -1;
        if(nums==null|| nums .length==0){
            return result;
        }
        int start = 0;
        int end = nums.length-1;
        while(end>= start){
            int mid = start+(end-start)/2;
            if(nums[mid] == target){
                result[0] = mid;
                int endIndex = mid;
//                System.out.println("mid+1 ="+(mid+1));
//                System.out.println("end ="+end);
                while(mid+1<=end && nums[mid+1]==target ){
                    endIndex = mid+1;
                    mid++;
                }
                result[1] = endIndex;
                return result;
            }else if(nums[mid]>target){
                end = mid -1;
            }else {
                start = mid +1;
            }
        }
        return result;
    }

    /**
     * 如何高效对有序数组/链表去重？ 返回去重之后的数组长度
     * 给定数组{0,0,1,1,1,2,3,3,3} 返回去重之后的数组长度
     */
    @Test
    public void testgetLength(){
        int nums[] ={0,0,1,1,1,2,3,3,3,4,5,6};
        int length = getLength(nums);
        System.out.println(length);
    }
    public static int getLength(int [] nums){
        if(nums == null || nums.length==0){
            return 0;
        }
        int slow = 0;
        int fast = 1;
        int length = nums.length;
        for(int i=0;i<nums.length;i++){
            if(nums[slow] == nums[fast]){
                length = length-1;
            }
            if(fast+1<nums.length-1){
                slow++;
                fast++;
            }
        }

        return length;
    }


    /**
     * 输入: [3,2,1,5,6,4] 和 k = 2
     * 1 2 3 4 5 6
     * 输出: 5
     * k=2 按最小排的话 应该放在下标为nums,leng-2
     */
    @Test
    public void testgetLarge(){
        int nums [] = {3,2,1,5,6,4};
        System.out.println(getLarge(nums,2));
    }
    public static int getLarge(int nums[],int k ){
        if(nums==null || nums.length==0 || k<=0){
            throw new RuntimeException("输入非法");
        }
        int result = quickSort(nums, 0, nums.length - 1, k);
        return result;
    }

    public static int quickSort(int nums[],int start,int end,int k){
        int result  = 0;
        // 1 2 3 4 5 6
        int mid  = partition1(nums,start,end);
        while (true){
            if(mid == nums.length-k){
                result = nums[mid];
                break;
            }else if(mid>nums.length-k) {
               mid = partition1(nums, start, mid - 1);
            }else {
                mid =  partition1(nums,mid+1,end);
            }
        }


        return result;
    }

    private static int partition1(int[] nums, int start, int end) {
        Arrays.copyOfRange(nums,0,nums.length);
        int stadarnd = nums[start];
        int temp = start;
        for(int i = start+1;i<=end;i++){
            if(nums[i]<stadarnd){
                temp++;
                swap(nums,i,temp);
            }
        }
        Stack<Character> stack = new Stack<>();
        swap(nums,start,temp);
        return temp;
    }

    /**
     *     //快慢指针 ***
     *
     *     //lru算法 ****
     *
     *     // topK算
     *
     *     //给定两个数组，编写一个函数来计算它们的交集。
     *
     */














    /**
     * //归并排序
     */
    @Test
    public void testsort()  {
        int nums[] = {4,3,1,5,6,81,7,1100,-1,2,-3};
        mergeSortUp2Down(nums,0,nums.length-1);
        print(nums);
    }
    public static int[] sort(int[] sourceArray)  {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        if (arr.length < 2) {
            return arr;
        }
        int middle = arr.length / 2;

        int[] left = Arrays.copyOfRange(arr, 0, middle);
        int[] right = Arrays.copyOfRange(arr, middle, arr.length);

        return merge(sort(left), sort(right));
    }

    protected static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int i = 0;
        while (left.length > 0 && right.length > 0) {
            if (left[0] <= right[0]) {
                result[i++] = left[0];
                left = Arrays.copyOfRange(left, 1, left.length);
            } else {
                result[i++] = right[0];
                right = Arrays.copyOfRange(right, 1, right.length);
            }
        }

        while (left.length > 0) {
            result[i++] = left[0];
            left = Arrays.copyOfRange(left, 1, left.length);
        }

        while (right.length > 0) {
            result[i++] = right[0];
            right = Arrays.copyOfRange(right, 1, right.length);
        }

        return result;
    }

    public static void mergeSortUp2Down(int[] elem, int start, int end) {
        if(elem == null || start >= end) {
            return;
        }

        int mid = (start + end) / 2;

        mergeSortUp2Down(elem, start, mid);
        mergeSortUp2Down(elem, mid + 1, end);

        merge(elem, start, mid, end);
    }

    public static void merge(int[] elem, int start, int mid, int end) {
        int[] temp = new int[end - start + 1];
        int i = start;
        int j = mid + 1;
        int k = 0;
        while(i <= mid && j <= end) {
            if(elem[i] < elem[j]) {
                temp[k++] = elem[i++];
            }
            else {
                temp[k++] = elem[j++];
            }
        }

        while(i <= mid) {
            temp[k++] = elem[i++];
        }

        while(j <= end) {
            temp[k++] = elem[j++];
        }

        for (i = 0; i < k; i++) {
            elem[start + i] = temp[i];
        }
        temp = null;
    }
}
